#include <iostream>
#include <algorithm>

using namespace std;

int dp[100005] = {0};
int arr[100005] = {0};

int gcd(int a,int b){
	return b == 0 ? a : gcd(b, a % b);
}

int main(){
	
	int n;
	cin >> n;
	
	cin >> arr[0];
	if(arr[0] != 1) dp[0] = 1;
	
	for(int i = 1; i < n; ++i){
		cin >> arr[i];
		for(int j = 0; j < i; ++j){
			if(arr[j] == 1 || gcd(arr[j],arr[i]) > 1){
				dp[i] = max(dp[i],dp[j] + 1);
			}else{
				dp[i] = max(dp[i],dp[j]);
			}
		}
	}
	
	cout << dp[n - 1];

	return 0;
}

